package sortAlgorithm;

import java.util.Arrays;
import java.util.Random;

public class InsertSort {
	public static void main(String[] args) {
		long now = System.currentTimeMillis();
		Random random = new Random();
		int[] a = new int[300];
		int[] b = new int[300];
		for (int i = 0; i < a.length; i++) {
			a[i]=random.nextInt(200);
			b[i]=random.nextInt(200);
		}
		System.out.println("排序前：");
		System.out.println(Arrays.toString(a));
		System.out.println("排序后：");
		insertSort(a,a.length-1);
		System.out.println(Arrays.toString(a));
		System.out.println("耗时："+(System.currentTimeMillis()-now)+" ms");
		System.out.println("排序前：");
		System.out.println(Arrays.toString(b));
		System.out.println("排序后：");
		insertSort1(b);
		System.out.println(Arrays.toString(b));
		System.out.println("耗时："+(System.currentTimeMillis()-now)+" ms");
	}
	public static void insertSort(int[] array,int end) {
		if(end==0) {
			return;
		}
		insertSort(array,end-1);
		int k=array[end];
		int index =end-1;
		while(index>-1&&k<array[index]) {
			array[index+1]=array[index];
			index--;
		}
		array[index+1]=k;
	}
	//递推形式
	public static void insertSort1(int[] array){
		for (int i = 1; i < array.length; i++) {
			int k = array[i];
			int index = i -1;
			while(index>-1&&k<array[index]){
				array[index+1] = array[index];
				index--;
			}
			array[index+1] = k;
		}
	}
}
